package leetcode.stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Description: https://leetcode.cn/problems/sliding-window-maximum/
 * @Author Ammar
 * @Create 2023/7/11 17:52
 */
public class _239_滑动窗口最大值 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) return nums;
        Deque<Integer> deque = new LinkedList<>();
        int ri = 0;
        int li = 1 - k;
        int[] maxes = new int[nums.length - k + 1];
        while (ri <= nums.length - 1) {
            while (!deque.isEmpty() && nums[deque.getLast()] <= nums[ri]) {
                deque.removeLast();
            }
            deque.addLast(ri);

            if (li < 0) {
                li++;
                ri++;
                continue;
            }
            Integer index = deque.getFirst();
            if (li > index) {
                deque.removeFirst();
                index = deque.getFirst();
            }
            maxes[li] = nums[index];
            li++;
            ri++;
        }
        return maxes;
    }
}
